import java.util.ArrayList;
import java.util.Random;


public class QSortJ {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		long start = System.currentTimeMillis();

		// 乱数の配列生成
		ArrayList<Integer> list = new ArrayList<Integer>();

		Random random = new Random();
		for (int i = 0; i < 10000; i++ ) {
			list.add(random.nextInt(10000));
		}

		ArrayList<Integer> afterSortList = quickSort(list);

		System.out.println(afterSortList);

		long end = System.currentTimeMillis();

		System.out.println(end-start + "msec");
	}

	private static ArrayList<Integer> quickSort(ArrayList<Integer> data) {

		if (data.size() < 1) { return new ArrayList<Integer>(); }

	    Integer middle = data.get(data.size() / 2);

	    ArrayList<Integer> left   = new ArrayList<Integer>();

	    ArrayList<Integer> right  = new ArrayList<Integer>();

	    for(int i = 0, n = data.size(); i < n; i++) {
	    	if(i != data.size() / 2) {
		        if(data.get(i) <= middle) {  // leftward, rightward spreading
		        	left.add(data.get(i));
		        } else {
		        	right.add(data.get(i));
		        }
	    	}
	    }

	    ArrayList<Integer> result = new ArrayList<Integer>();
	    result.addAll(quickSort(left));
	    result.add(middle);
	    result.addAll(quickSort(right));

	    return result;
	}
}
